package no38;

import java.util.*;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/20 9:07
 * 字符串的排列
 * https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/
 * 目前实现的方式为深度回溯算法+set去重,  暂时未实现剪枝的逻辑
 */
public class Solution {

    public static void main(String[] args) {
        String s = "aab";
        String[] permutation = new Solution().permutation(s);
        System.out.println(Arrays.toString(permutation));
    }

    public String[] permutation(String s) {
        Set<String> res = new HashSet<>();
        StringBuilder temp = new StringBuilder();
        boolean[] visited = new boolean[s.length()];
        dfs(s.toCharArray(), visited, temp, res);
        String[] ret = new String[res.size()];
        int index = 0;
        for (String item : res) {
            ret[index++] = item;
        }
        return ret;
    }

    // 深度搜索
    private void dfs(char[] chars, boolean[] visited, StringBuilder temp, Set<String> res) {
        if (temp.length() == chars.length) {
            // 记录结果
            res.add(temp.toString());
            return;
        }
        // 深度回溯
        for (int i = 0; i < chars.length; i++) {
            if (!visited[i]) {
                // 如果没有被访问过
                temp.append(chars[i]);
                visited[i] = true; // 标记已经被访问过
                dfs(chars, visited, temp, res);
                visited[i] = false; // 恢复初始状态
                temp.deleteCharAt(temp.length()-1);
            }
        }
    }
}
